M - Candies

考察

とりあえずテーブル予想

でもこれじゃ明らかに情報が足りなさすぎる

紙に書いてみる

個数が少ない所をどう考えるか、分からないのでとりあえず紙に書き出してみる

K=5, a={3,5,2}で手元で求めてdp配列の中身を書いてみる

https://gyazo.com/8f1eef4499ab09119955be55d57e3170

ここで(2,5)の姿を考えてみることにする。つまり、2人目(0-indexed)までに5つ配る組み合わせ。

適当にアフターの絵を描いてみる

https://gyazo.com/aefc5092764c155c6e282c1a565bacbc

これまでの計算結果を利用して(2,5)の答えを求めたい。計算結果とは、それより前の「〜人目までで、j個配るときの組み合わせの数」みたいなやつ。

よーく図を見ると、2人目に配る飴が1つのとき、それより左側では合計で4つの飴を配ってる、

他にも2人目に配る飴が2つのとき、それより左側では合計で3つの飴を配ってる

https://gyazo.com/30fc447dca2aa86c4bffc99786e67e25

まあなので、遷移としては一つ前までのやつの区間和を求めたくて、でもそれをしちゃうと時間がかかるので、累積和で高速化します